Diviseurs du PGCD

Propriété

Soit \(a \in \mathbb{Z}\) et \(b \in \mathbb{Z}\) tels que \((a;b) \neq (0;0)\) . On note \(d=\mathrm{PGCD}(a;b)\) .

L'ensemble des diviseurs communs de \(a\) et \(b\) est exactement l'ensemble des diviseurs de \(d\) , c'est-à-dire : \(\mathscr{D}(a;b)=\mathscr{D}(d)\) .

Autrement dit, pour tout \(n \in \mathbb{Z}\) , \(n\) divise \(a\) et \(b\) si, et seulement si, \(n\) divise \(d\) .

Démonstration

En appliquant l'algorithme d'Euclide et en utilisant le lemme d'Euclide à chaque étape, on obtient :
\(\begin{align*} \mathscr{D}(a;b) &=\mathscr{D}(b;r_1) \\ & =\mathscr{D}(r_1;r_2) \\ & = \ ... \\ & =\mathscr{D}(r_{n-2};r_{n-1}) \\ & =\mathscr{D}(r_{n-1};0) \\ & =\mathscr{D}(r_{n-1}) \end{align*}\)  
avec \(r_{n-1}=\mathrm{PGCD}(a;b)\) .